An integrated circuit (“IC”) is a device (e.g., a semiconductor device) that includes many electronic components, such as transistors, resistors, diodes, etc. These components are often interconnected to form multiple circuit components, such as gates, cells, memory units, arithmetic units, controllers, decoders, etc. An IC includes multiple layers of wiring that interconnect its electronic and circuit components. Traditionally, IC's use preferred direction (“PD”) wiring models, which specify a preferred wiring direction for each of their wiring layers. In preferred direction wiring models, the preferred direction typically alternates between successive wiring layers. One example of a PD wiring model is the PD Manhattan wiring model, which specifies alternating layers of preferred-direction horizontal and vertical wiring.
Wiring models have been proposed that allow wiring in diagonal directions (e.g., one wiring model allows wiring in horizontal, vertical, and ±45° diagonal directions). Some of these wiring models are non-preferred direction (“NPD”) wiring models. An NPD wiring model has at least one NPD wiring layer, on which two or more wiring directions are equally preferable and are at least as preferable as all other wiring directions on that layer.
Engineers design IC's by transforming logical or circuit descriptions of the IC's into geometric descriptions, called layouts. IC layouts typically include (1) circuit modules (i.e., geometric representations of electronic or circuit IC components) with pins, and (2) interconnect lines (i.e., geometric representations of wiring) that connect the pins of the circuit modules. A net is typically defined as a collection of pins that need to be connected. A list of all or some of the nets in a layout is referred to as a net list.
To create layouts, design engineers typically use electronic design automation (“EDA”) applications. These applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts. The IC design process entails various operations. One of these operations is placement, which is the process of arranging the circuit modules on a layout in order to achieve certain objectives, such as reducing layout area, wirelength, wire congestion, etc.
Numerous EDA placers have been proposed to date. Many placers try to reduce expected length of wires for routing nets. A wirelength minimization problem includes as given n modules with areas a1, a2, . . . , an, and m edges e1, e2, . . . em where edge ei has importance bi and links module ei1 to module ei2. A placement typically specifies a location (xj,yj) for each module j within a specified two-dimensional space. The importance-weighted wire length measure is:
            ∑              i        =        1            m        ⁢                  b        i            ⁢              L        ⁡                  (                                                    x                                  e                                      i                    ⁢                                                                                  ⁢                    2                                                              -                              x                                  e                                      i                    ⁢                                                                                  ⁢                    1                                                                        ,                                          y                                  e                                      i                    ⁢                                                                                  ⁢                    2                                                              -                              y                                  e                                      i                    ⁢                                                                                  ⁢                    1                                                                                )                      ,where L(x,y) is the minimum wire length needed to connect (0,0) to (x,y). The objective is to minimize this importance-weighted wire length measure, subject to constraints. A typical constraint is that, within a sub-region of the placement, the total component area does not exceed the area of the sub-region.
Certain placers are analytical placers. An analytical placer typically performs the following three operations. First, it formulates an objective function to express the placement of one or more circuit elements (e.g., circuit modules) in a layout. Second, the placer solves the objective function to identify a placement. Third, it iteratively specifies additional placement constraints and performs the first two operations until it reaches a condition for terminating the iterations.
Examples of analytical placers include quadratic and linear placers. Quadratic placers use the sum of the squared Euclidean distance between each pair of pins of each net as the objective function. This objective function is expressed by the following formula:
      Function    =                  ∑        n            ⁢                        ∑                      p            ⁡                          (              n              )                                      ⁢                              b                          i              ,              j                                ⁡                      (                                                            (                                                            x                      i                                        -                                          x                      j                                                        )                                2                            +                                                (                                                            y                      i                                        -                                          y                      j                                                        )                                2                                      )                                ,where n represents a net, p(n) represents a unique pair of pins i and j of the net n, x and y represent the x-, and y-coordinates of a particular pin, and bi,j represents a weighting factor that biases the function based on the desired closeness of pins i and j. Linear placers use the Manhattan distance between each pair of pins of each net as the objective function. This objective function is expressed by the following formula:
  Function  =            ∑      n        ⁢                  ∑                  p          ⁡                      (            n            )                              ⁢                                    b                          i              ,              j                                ⁡                      (                                                                                                x                    i                                    -                                      x                    j                                                                              +                                                                                    y                    i                                    -                                      y                    j                                                                                        )                          .            
Prior analytical placers do not consider the possibility of diagonal wiring. Hence, these techniques result in poor placement configurations for routers that use diagonal wiring. Such placement configurations inefficiently consume the layout area, utilize too much wire, and/or have poor wire congestions. Consequently, there is a need in the art for analytical placers that consider the possible use of diagonal wiring during routing.